#include <string>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

// 1138.字母板上的路径
class Solution1
{
public:
    string alphabetBoardPath(string target) 
    {
        string ret;
        int x = 0, y = 0;
        for(char ch : target)
        {
            int nx = (ch - 'a') / 5, ny = (ch - 'a') % 5;
            string v(abs(nx - x), "UD"[nx > x]);
            string h(abs(ny - y), "LR"[ny > y]);
            ret += (ch != 'z' ? v + h : h + v) + "!";
            x = nx, y = ny;
        }
        return ret;
    }
};

// 2521. 数组乘积中的不同质因数数目
class Solution2
{
public:
    int distinctPrimeFactors(vector<int>& nums) 
    {
        unordered_set<int> s;
        for(int x : nums)
        {
            for(int i = 2; i * i <= x; ++i)
            {
                if(x % i == 0)
                {
                    s.insert(i);
                    while(x % i == 0) x /= i;
                }
            }
            if(x > 1) s.insert(x);
        }

        return s.size();
    }
};

// 2383. 赢得比赛需要的最少训练时长
class Solution3
{
public:
    int minNumberOfHours(int initialEnergy, int initialExperience, vector<int>& energy, vector<int>& experience) 
    {
        int ret = 0;
        int sum = accumulate(energy.begin(), energy.end(), 0);
        if(initialEnergy <= sum) ret += sum - initialEnergy + 1;
        for(int i = 0; i < experience.size(); ++i)
        {
            if(initialExperience <= experience[i]) 
            {
                ret += (experience[i] - initialExperience + 1);
                initialExperience += 2 * experience[i] - initialExperience + 1;
            }
            else
                initialExperience += experience[i];
        }
        return ret;
    }
};

